from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        profit = 0
        stack = [prices[0]]
        for x in prices[1:]:
            if len(stack) == 2:
                if x >= stack[-1]:
                    stack.pop()
                    stack.append(x)
                else:
                    profit += stack[1] - stack[0]
                    stack = [x]
            elif len(stack) == 1:
                if x <= stack[-1]:
                    stack = [x]
                else:
                    stack.append(x)
        if len(stack) == 2:
            profit += stack[1] - stack[0]
        return profit


prices = [7,1,5,3,6,4]
print(Solution().maxProfit(prices))
prices = [1,2,3,4,5]
print(Solution().maxProfit(prices))
prices = [7,6,4,3,1]
print(Solution().maxProfit(prices))
